import java.util.*;

/**
 * Created by zhourh on 2018/6/11.
 *
 * 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

 nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。

 栈
 */
public class NextGreaterElement {

    public static void main(String[] args) {
        int[] nums1 = new int[]{4,1,2};
        int[] nums2 = new int[]{1,3,4,2};
        int[] result = new NextGreaterElement().nextGreaterElement(nums1, nums2);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + "," );
        }
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack();
        Map<Integer, Integer> resultMap = new HashMap();

        for (int num : nums2) {
            while (stack.size() > 0 && stack.peek() < num) {
                resultMap.put(stack.peek(), num);
                stack.pop();
            }

            stack.push(num);
        }

        int[] result = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            result[i] = resultMap.getOrDefault(nums1[i], -1);
        }

        return result;
    }

    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        if (nums1 == null || nums1.length == 0) {
            return result;
        } else if (nums2 == null || nums2.length == 0) {
            Arrays.fill(result, -1);
            return result;
        }

        Arrays.fill(result, -1);
        List<Integer> nums2List = new ArrayList();
        for (int i = 0; i < nums2.length; i++) {
            nums2List.add(nums2[i]);
        }
        for (int i = 0; i < nums1.length; i++) {
            for (int j = nums2List.indexOf(nums1[i]) + 1; j < nums2List.size(); j++) {
                if (nums2List.get(j) > nums1[i]) {
                    result[i] = nums2List.get(j);
                    break;
                }
            }
        }

        return result;

    }
}
